package 线段树And树状数组;
/**
 * 手写 一下 线段树       面试厂 上 这些 东西 一定 十分熟悉的 手写出来
 * @author I adore you
 * 首先 解释  这个 sum 数组 的 含义：
 *在线段树 中所有声明的 的数组 下标 0  都是 弃之不用的
 * 
 * sum[i] = l ~ r 的范围和           每一个  下标      i  对应 着一个范围
 * sum[1] 表示的 范围是   1~ len  范围上的 和
 * 注意 这个 sum 对应的 其实 是一个  满二叉树  人为 补满 的一个 完全二叉树
 *  数组长度   4N 的解释 ： 可以 容纳 所有情况的 len      值
 *  1. N = 2 ^  len 此时是最省空间的 2N 就足够 
 *  2.最不省空间的 是 比如 len =5；  N为 8 时 画一下  这个完全二叉树 就知道 为啥了
 * 为啥 让数组的下标 从    1  而不是 0  开始  就是为了 运用位运算  快 （fast）
 * index<<1 =index *2          index<<1 | 1 =  index*2+1;
 * 
 * 
 *
 */

public class SelentMentTree {
	private int origin[];
	 int sum[];
	private int lazy[];
	private int change[];
	private boolean update[];
	/**
	 * 初始化   这个 线段树的  容量
	 * @param arr
	 */
	public SelentMentTree(int arr[]) {
		int len = arr.length;
		origin = new int [len+1];
		for(int i = 1 ;i <=len;i++) {
			origin[i] = arr[i-1];
		}
		sum = new int[len<<2];
		lazy = new int [len<<2];
		change = new int [len<<2];
		update = new boolean [len<<2];
	}
	public SelentMentTree() {
		
	}
	
//	 这个函数 是可以 省掉的 不用  写 对吧 树形DP的经典案例
	public void pushSum(int scaleIndex) {
		sum[scaleIndex] = sum[scaleIndex << 1] + sum[scaleIndex << 1 | 1];
	}
	public void sum(int l,int r,int scaleIndex) {
//		  这里 需不需要 添加 一些 过滤条件   去掉  不合理 的情况
		if(l == r) {
//		 到达叶子 节点 
		sum[scaleIndex] = origin[l];
		return ;
		}
//		  将范围  进行二分
		int mid = l+((r-l)>>1); // 防止 溢出 并且 快
		sum(l,mid,scaleIndex << 1);
//		  这里 时 mid+1  要注意 一下
		sum(mid+1,r,scaleIndex << 1 |1);
//		  写到这里 并没有 结束呢    这有点 相似 树形DP对吧              左节点           右节点         然后 汇总 父节点
//		pushSum(scaleIndex);
		sum[scaleIndex] = sum[scaleIndex << 1] + sum[scaleIndex << 1 | 1];  //尝试 一下
	}
//	  添加 和 update 的 函数 要 稍微 复杂 一些
	/**
	 * 这个 lazy 数组 在这里 发挥 着 很重要的作用 
	 * 
	 * @param l   这俩 表示 的是 数组 范围 的边界 
	 * @param r
	 * @param scaleIndex
	 * @param L   这俩 表示 在 L ~ R 范围内  直接 add 个 value 
	 * @param R
	 * @param value   添加的 值
	 */
	public void add(int l,int r,int scaleIndex,int L,int R,int value) {
		if(L<=l && r <=R ) {
//		  这说明 啥  没必要 分发 直接 揽住了 在 本层  就可以 直接 解决了  这不就是 提高 效率的地方嘛
			sum[scaleIndex] += (r-l+1)*value;
			lazy[scaleIndex] += value;
			
			return ;
		}
//		下面是 揽不住 的情况  既然 揽 不住  就下发 pushDown
		int mid = l + ((r - l)>>1);
		pushDown(scaleIndex,mid-l+1,r-mid);
		if(L <= mid) {
//			pushDown(r,l,scaleIndex,value);
			add(l,mid,scaleIndex<<1,L,R,value);
		}
		if(R > mid) {
			add(mid+1,r,scaleIndex<<1|1,L,R,value);
		}
		pushSum(scaleIndex);
	}
	public void update(int l,int r,int scaleIndex,int L,int R,int value) {
		if(L<=l && r <=R ) {
			sum[scaleIndex] = (r-l+1)*value;
			change[scaleIndex] = value;
			update[scaleIndex] = true;
			lazy[scaleIndex] = 0;
			return ;
		}
		int mid = (r+l)>>1;
		pushDown(scaleIndex,mid-l+1,r-mid);
		if(L <= mid ) {
			update(l,mid,scaleIndex<<1,L,R,value);
			
		}
		if(R > mid) {
			update(mid+1,r,scaleIndex<<1|1,L,R,value);
		}
		pushSum(scaleIndex);
	}
	
	public long query(int l,int r,int scaleIndex,int L,int R) {
		if(L <= l && r <= R) {
			return sum[scaleIndex];
		}
		int mid = (l+r)>>1;
		pushDown(scaleIndex,mid-l+1,r-mid);
		long ans =0L;
		if(L <= mid) {
			ans += query(l,mid,scaleIndex<<1,L,R);
		}
		if( R > mid) {
			ans += query(mid+1,r,scaleIndex<<1|1,L,R);
		}
		return ans;

	}
	
	
/**
 * 
 * @param scaleIndex 范围对应 下 标
 * @param value  添加的值    不需要 这个 value的值  而且 也不能写  否则 会出现 一些 问题比如在 query 就没办法传入参数了
 * 这个 也是 很好 解决的对吧  当需要 分发的时候  lazy  和 change 数组 中都是记录 相应 的值的
 * @param ln  mid-l+1 ;
 * @param rn  r-mid  就是 子范围的 内的个数 count
 */
	public void pushDown(int scaleIndex,int ln,int rn) {
		if(update[scaleIndex]) {
			lazy[scaleIndex<<1] = 0;
			lazy[scaleIndex<<1|1] = 0;
			
			sum[scaleIndex<<1] = ln*change[scaleIndex];
			sum[scaleIndex<<1|1] = rn*change[scaleIndex];
			
			change[scaleIndex<<1] = change[scaleIndex];
			change[scaleIndex<<1|1] = change[scaleIndex];
			
			update[scaleIndex<<1]  = true;
			update[scaleIndex<<1|1] = true;
			
			update[scaleIndex] = false;
//			change[scaleIndex] = 0;
		}
		if(lazy[scaleIndex]!=0) {
			sum[scaleIndex<<1] += lazy[scaleIndex]*ln;
			sum[scaleIndex<<1|1] += lazy[scaleIndex]*rn;
			lazy[scaleIndex<<1] += lazy[scaleIndex];
			lazy[scaleIndex<<1|1] += lazy[scaleIndex];
			lazy[scaleIndex] = 0;
		}
	}
	
	
	
	
	public static void main(String []args) {
		int arr[] = {1,2,3,4,5};
		SelentMentTree tree = new SelentMentTree(arr);
		tree.sum(1,arr.length,1);
		System.out.println(tree.sum[1]);
		tree.add(1, 5, 1, 1, 5, 2);
		System.out.println(tree.sum[1]);
		tree.update(1, 5, 1, 3, 3, 2);
		System.out.println(tree.query(1, 5, 1, 1, 5));
	}
}
